O(n^2)时间复杂度的排序算法实现

发布于   |   分类于   |     |   阅读次数

插入排序

特点

若数组基本有序时，插入排序效率很高。插入排序具有稳定性。

思路

每次向已有序的数组中插入当前的数，相当于将已有序数组中大于当前数的所有数向后挪一个位置。
i表示当前插入的数的下标，j从已有序数组的最大的数的下标逐渐递减。

代码

1
2
3
4
5
6
7
8
9
void insertSort(vector<int> &a){
    for(int i = 1; i < a.size(); i++){
        int j, t = a[i];
        for(j = i-1; j>=0 && a[j]>t; j--){
            a[j+1] = a[j];
        }
        a[j+1] = t;
    }
}

选择排序

思路

每次从当前位置以及之后的位置中找到一个最小的数与当前位置的数交换。
i是当前位置的下标，j遍历所有大于i的下标。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void selectSort(vector<int> &a){
    for(int i = 0; i < a.size()-1; i++){
        int t = i;
        for(int j = i+1; j < a.size(); j++){
            if(a[j] < a[t]){
                t = j;
            }
        }
        int tmp = a[i];
        a[i] = a[t];
        a[t] = tmp;
    }
}

冒泡排序

思路

每次将两个数比较，如果前面的数较大，将其交换位置，每轮可以让一个大数沉底。
i遍历冒泡轮次，j遍历两个数中前一个数的下标。

代码

1
2
3
4
5
6
7
8
9
10
11
void bubbleSort(vector<int> &a){
    for(int i = 0; i < a.size()-1; i++){
        for(int j = 0; j < a.size()-1-i; j++){
            if(a[j] > a[j+1]){
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}